{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "partial-basket",
   "metadata": {},
   "source": [
    "# Simulating the Deutsch–Jozsa algorithm with noise"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "random-sequence",
   "metadata": {},
   "source": [
    "## Abstract"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "subjective-motor",
   "metadata": {},
   "source": [
    "In this sample, we'll look at how noise in quantum devices may affect quantum algorithms such as the _Deutsch–Jozsa algorithm_, using the open systems simulator provided with the Quantum Development Kit to test Q# applications against different kinds of noise.\n",
    "\n",
    "> **💡 TIP:** To learn more about the Deutsch–Jozsa algorithm check out the [**getting-started/simple-algorithms** sample](https://github.com/microsoft/Quantum/blob/main/samples/getting-started/simple-algorithms/README.md)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ultimate-variety",
   "metadata": {},
   "source": [
    "## Preamble"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "amber-consent",
   "metadata": {},
   "source": [
    "We start by importing the interoperability package that allows for calling into Q# from Python. This package allows us to define Q# functions and operations from within Python notebooks, and to simulate running quantum programs on various different simulators. This can take 15 seconds to run the first time, as the Q# environment is initializing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "reserved-cheat",
   "metadata": {},
   "outputs": [],
   "source": [
    "import qsharp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "medieval-flower",
   "metadata": {},
   "source": [
    "## Deutsch–Jozsa without noise"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "subtle-exhibition",
   "metadata": {},
   "source": [
    "Before seeing how the Deutsch–Jozsa algorithm works in the presence of noise, it helps to first test that our implementation is correct when run on an ideal (noiseless) quantum device. To do so, we'll start by writing an implementation of the Deutsch–Jozsa algorithm using the `%%qsharp` magic command. This can take 15 seconds to run the first time, as the Q# environment is initializing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "utility-blame",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%qsharp\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Convert;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "certified-speech",
   "metadata": {},
   "source": [
    "The main part of our implementation will be an operation that applies an oracle to a register in the $\\left|++\\cdots+-\\right\\rangle$ state, such that phase kickback from the last qubit can be observed on the control register.\n",
    "\n",
    "Suppose that the oracle can be simulated by a unitary operator $U_f \\left|x\\right\\rangle \\left|y\\right\\rangle = \\left|x\\right\\rangle \\left|y \\oplus f(x) \\right\\rangle$. Then, if $f(x)$ is a constant function such that $f(x) = s$ for all $x$, we have that\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    U_f \\left|++\\cdots+-\\right\\rangle & = \\frac{1}{\\sqrt{2^n}} \\left[\n",
    "        (-1)^s \\left|00\\cdots0\\right\\rangle +\n",
    "        (-1)^s \\left|00\\cdots1\\right\\rangle +\n",
    "        (-1)^s \\left|01\\cdots0\\right\\rangle +\n",
    "        (-1)^s \\left|01\\cdots1\\right\\rangle + \\cdots\n",
    "    \\right] \\otimes \\left|-\\right\\rangle \\\\\n",
    "    & = (-1)^s \\left|++\\cdots+-\\right\\rangle,\n",
    "\\end{aligned}\n",
    "$$\n",
    "where $n$ is the size of the register that our oracle acts on. Since $(-1)^s$ is a global phase, it has no effect on any measurement outcomes, such that we can measure the control register to see if it was left in the $\\left|++\\cdots+\\right\\rangle$ state by applying our oracle. If so, then we can conclude that $f$ must have been constant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "earlier-sculpture",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%qsharp\n",
    "operation MeasureIfConstantBooleanFunction(oracle : ((Qubit[], Qubit) => Unit), n : Int) : Bool {\n",
    "    use queryRegister = Qubit[n];\n",
    "    use target = Qubit();\n",
    "\n",
    "    // The last qubit needs to be flipped so that the function will\n",
    "    // actually be computed into the phase when Uf is applied.\n",
    "    X(target);\n",
    "    H(target);\n",
    "\n",
    "    within {\n",
    "        ApplyToEachA(H, queryRegister);\n",
    "    } apply {\n",
    "        // We now apply Uf to the n + 1 qubits, computing |𝑥, 𝑦〉 ↦ |𝑥, 𝑦 ⊕ 𝑓(𝑥)〉.\n",
    "        oracle(queryRegister, target);\n",
    "    }\n",
    "\n",
    "    let resultArray = ForEach(MResetZ, queryRegister);\n",
    "    Reset(target);\n",
    "\n",
    "    return All(IsResultZero, resultArray);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "historical-treasurer",
   "metadata": {},
   "source": [
    "Next, we need a Q# operation to represent the oracle itself. To do so, we'll consider an oracle representing the function\n",
    "$$\n",
    "    f(x) = \\begin{cases}\n",
    "        1 & x \\in S \\\\\n",
    "        0 & \\text{otherwise}\n",
    "    \\end{cases}\n",
    "$$\n",
    "for some set of marked inputs $S$. That is, where $f$ is specified by a list of values for which $f(x) = 1$. Using this representation, we can apply our oracle to a given register using the [`ControlledOnInt` function](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "prerequisite-affiliation",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%qsharp\n",
    "operation ApplyOracle(n : Int, markedElements : Int[], query : Qubit[], target : Qubit) : Unit {\n",
    "    for markedElement in markedElements {\n",
    "        // Note: As X accepts a Qubit, and ControlledOnInt only\n",
    "        // accepts Qubit[], we use ApplyToEachCA(X, _) which accepts\n",
    "        // Qubit[] even though the target is only 1 Qubit.\n",
    "        ControlledOnInt(markedElement, ApplyToEachCA(X, _))(query, [target]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "closed-advertiser",
   "metadata": {},
   "source": [
    "Finally, we can use the two operations we defined above to run the Deutsch–Jozsa algorithm for an oracle given by a list of marked elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "coupled-yorkshire",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Not required, but can be helpful to provide type information\n",
    "# to some IDEs.\n",
    "RunDeutschJozsa: qsharp.QSharpCallable = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "italian-hanging",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%qsharp\n",
    "operation RunDeutschJozsa(nQubits : Int, markedElements : Int[]) : Bool {\n",
    "    return MeasureIfConstantBooleanFunction(\n",
    "        ApplyOracle(nQubits, markedElements, _, _),\n",
    "        nQubits\n",
    "    );\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "thick-education",
   "metadata": {},
   "source": [
    "For two qubits, marking `[]` and `[0, 1, 2, 3]` represent constant functions while lists of marked inputs such as `[0, 1]` `[2, 3]` represent balanced functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "roman-stereo",
   "metadata": {},
   "outputs": [],
   "source": [
    "RunDeutschJozsa(nQubits=2, markedElements=[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "israeli-cement",
   "metadata": {},
   "outputs": [],
   "source": [
    "RunDeutschJozsa(nQubits=2, markedElements=[0, 1, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "wrong-medline",
   "metadata": {},
   "outputs": [],
   "source": [
    "RunDeutschJozsa(nQubits=2, markedElements=[0, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apparent-growing",
   "metadata": {},
   "source": [
    "## Simulating with noise"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "located-envelope",
   "metadata": {},
   "source": [
    "To see how the Deutsch–Jozsa algorithm performs in the presence of noise, we can use the open systems simulator provided with the Quantum Development Kit."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "innocent-luxembourg",
   "metadata": {},
   "source": [
    "The open systems simulator can be configured to use different kinds of noise by using the [QuTiP library](https://qutip.org/) to describe noise models for quantum devices, so we'll go on and import that library here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "roman-awareness",
   "metadata": {},
   "outputs": [],
   "source": [
    "import qutip as qt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adult-attempt",
   "metadata": {},
   "source": [
    "For example, suppose that when the `H` operation is used, there's a small chance that it instead resets its input qubit to the $\\left|0\\right\\rangle$ state instead. We can model this as _amplitude damping noise_, using QuTiP to write out the relevant operator.\n",
    "\n",
    "> **💡 TIP:** To learn more about representing noise, check out the [open systems concept guide](https://github.com/microsoft/qsharp-runtime/blob/main/documentation/examples/open-systems-concepts.ipynb) provided with the Q# runtime.\n",
    "> To learn more about amplitude damping noise in particular, check out [the summary on Wikipedia](https://en.wikipedia.org/wiki/Amplitude_damping_channel).\n",
    "\n",
    "In particular, amplitude damping models a finite probability (represented below by `strength`) that the state of a qubit will be lost and replaced by $\\left|0\\right\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "primary-scene",
   "metadata": {},
   "outputs": [],
   "source": [
    "def amplitude_damping_channel(strength):\n",
    "    return qt.Qobj([\n",
    "        [1.0, 0.0, 0.0, strength],\n",
    "        [0.0, 1 - (strength / 2), 0.0, 0.0],\n",
    "        [0.0, 0.0, 1 - (strength / 2), 0.0],\n",
    "        [0.0, 0.0, 0.0, 1 - strength]\n",
    "    ], dims=[[[2], [2]], [[2], [2]]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "coordinate-secretary",
   "metadata": {},
   "source": [
    "We can then set the noise model for our open systems simulator to use amplitude damping noise to describe what happens when we call `H`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "proved-expression",
   "metadata": {},
   "outputs": [],
   "source": [
    "noise_model = qsharp.get_noise_model_by_name('ideal')\n",
    "noise_model.h = amplitude_damping_channel(strength=0.05) * qt.to_super(qt.qip.operations.hadamard_transform())\n",
    "qsharp.set_noise_model(noise_model)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "intensive-decrease",
   "metadata": {},
   "source": [
    "Whereas when running without noise, the Deutsch–Jozsa algorithm finds the right answer 100% of the time, noise causes our implementation to sometimes return the wrong answer; running 100 times, we thus won't see 100% accuracy in this case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "grave-continuity",
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(RunDeutschJozsa.simulate_noise(nQubits=2, markedElements=[0, 1, 2, 3]) for _ in range(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "thousand-vanilla",
   "metadata": {},
   "source": [
    "Of course, we use more than just the `H` operation in our Deutsch–Jozsa algorithm, so let's go on and add some noise to other operations as well. For example, `X` may introduce extra bit flip errors while `Z` may introduce extra phase flip errors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "arabic-racing",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bit_flip_channel(strength=0.05):\n",
    "    return (1 - strength) * qt.to_super(qt.qeye(2)) + strength * qt.to_super(qt.sigmax())\n",
    "def phase_flip_channel(strength=0.05):\n",
    "    return (1 - strength) * qt.to_super(qt.qeye(2)) + strength * qt.to_super(qt.sigmaz())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "abstract-colombia",
   "metadata": {},
   "outputs": [],
   "source": [
    "noise_model.x = bit_flip_channel() * qt.to_super(qt.sigmax())\n",
    "noise_model.z = phase_flip_channel() * qt.to_super(qt.sigmaz())\n",
    "qsharp.set_noise_model(noise_model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "engaging-allowance",
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(RunDeutschJozsa.simulate_noise(nQubits=2, markedElements=[0, 1, 2, 3]) for _ in range(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acknowledged-berkeley",
   "metadata": {},
   "source": [
    "## Further resources"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "effective-democrat",
   "metadata": {},
   "source": [
    "To learn more about the Deutsch–Jozsa algorithm, check out:\n",
    "\n",
    "- The [section on oracles](https://docs.microsoft.com/azure/quantum/concepts-oracles) in the Quantum Development Kit documentation.\n",
    "- Chapter 8 of [_Learn Quantum Computing with Python and Q#_](https://www.manning.com/books/learn-quantum-computing-with-python-and-q-sharp).\n",
    "- The [Deutsch–Jozsa kata](https://github.com/microsoft/QuantumKatas/tree/main/DeutschJozsaAlgorithm).\n",
    "\n",
    "To learn more about the open systems simulator, check out:\n",
    "\n",
    "- The [**characterization** samples](https://github.com/microsoft/Quantum/blob/main/samples/characterization/README.md).\n",
    "- The [section on noisy simulation](https://docs.microsoft.com/azure/quantum/user-guide/machines/noise-simulator) in the Quantum Development Kit documentation.\n",
    "- The [**open-systems-concepts** guide](https://github.com/microsoft/qsharp-runtime/blob/main/documentation/examples/open-systems-concepts.ipynb) provided with the Q# runtime."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sustainable-moisture",
   "metadata": {},
   "source": [
    "## Epilogue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "falling-wisdom",
   "metadata": {},
   "outputs": [],
   "source": [
    "qsharp.component_versions()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
